package com.lazycat.leetcode.editor.cn;
//2023-04-11 19:04:20
//给你一个下标从 0 开始的整数数组 nums 。现有一个长度等于 nums.length 的数组 arr 。对于满足 nums[j] == nums[i] 
//且 j != i 的所有 j ，arr[i] 等于所有 |i - j| 之和。如果不存在这样的 j ，则令 arr[i] 等于 0 。 
//
// 返回数组 arr 。 
//
// 
//
// 示例 1： 
//
// 
//输入：nums = [1,3,1,1,2]
//输出：[5,0,3,4,0]
//解释：
//i = 0 ，nums[0] == nums[2] 且 nums[0] == nums[3] 。因此，arr[0] = |0 - 2| + |0 - 3| 
//= 5 。 
//i = 1 ，arr[1] = 0 因为不存在值等于 3 的其他下标。
//i = 2 ，nums[2] == nums[0] 且 nums[2] == nums[3] 。因此，arr[2] = |2 - 0| + |2 - 3| 
//= 3 。
//i = 3 ，nums[3] == nums[0] 且 nums[3] == nums[2] 。因此，arr[3] = |3 - 0| + |3 - 2| 
//= 4 。 
//i = 4 ，arr[4] = 0 因为不存在值等于 2 的其他下标。
// 
//
// 示例 2： 
//
// 
//输入：nums = [0,5,3]
//输出：[0,0,0]
//解释：因为 nums 中的元素互不相同，对于所有 i ，都有 arr[i] = 0 。
// 
//
// 
//
// 提示： 
//
// 
// 1 <= nums.length <= 10⁵ 
// 0 <= nums[i] <= 10⁹ 
// 
//
// 👍 16 👎 0

import java.util.ArrayList;
import java.util.HashMap;

class SumOfDistances {
    public static void main(String[] args) {
        //创建该题目的对象方便调用
        Solution solution = new SumOfDistances().new Solution();
        solution.distance(new int[]{1,3,1,1,2});
    }
    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public long[] distance(int[] nums) {
        int n = nums.length;

        long[] ans = new long[n];

        HashMap<Integer, ArrayList<Integer>> hashMap = new HashMap<>();

        for(int i = 0;i<n;i++){

            if(!hashMap.containsKey(nums[i])){
                ArrayList<Integer> list = new ArrayList<>();
                list.add(i);
                hashMap.put(nums[i],list);
            }else {
                ArrayList<Integer> list = hashMap.remove(nums[i]);
                list.add(i);
                hashMap.put(nums[i],list);
            }
        }

        for(ArrayList<Integer> list : hashMap.values()){

            int m = list.size();
            long[] prefix = new long[m+1];

            for(int i = 1;i<=m;i++){
                prefix[i] = list.get(i-1) + prefix[i-1];
            }

            for(int i = 0;i<m;i++){
                int target = list.get(i);

                long left = (long) target * i - prefix[i];  //蓝色面积
                long right = prefix[m] - prefix[i] - (long) target * (m-i);   //绿色面积

                ans[target] = left + right;
            }
        }

        return ans;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}